package com.example.algorithm.tree;


// 本案例演示的是如何递归遍历树。这种遍历方法相对按层来遍历更简单一些。
// 遍历的结果打印出来。分别演示了前序、中序、后续遍历。每种遍历方式，最后打印出来的树节点的顺序不同。
// Traversal [træ'və:sl] 遍历
public class BinaryTreeTraversal {

    public static void main(String[] args) {
        // 创建一个二叉树
        // 就是一个普通的二叉树而已。没有什么顺序。
        //    3
        //9       20
        //    15       7
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        BinaryTreeTraversal traversal = new BinaryTreeTraversal();

        // 其实，对于一个普通的二叉树来讲，中序遍历并不能实现它的有序输出。

        // 前序遍历  是从父到子的。子的顺序也是从左到右的。最符合我们直觉的看树的习惯。一般用来拷贝树、序列化之类的。
        System.out.print("Preorder traversal: ");
        traversal.preorderTraversal(root);
        System.out.println();

        // 中序遍历。对于二叉查找树来说，中序最后可以保证打印的元素是有顺序的。
        System.out.print("Inorder traversal: ");
        traversal.inorderTraversal(root);
        System.out.println();

        // 后序遍历  后续遍历最后打印出来的顺序是，从下往上的。每个子树都遵循，先子后父。子的顺序都是从左到右。
        System.out.print("Postorder traversal: ");
        traversal.postorderTraversal(root);
        System.out.println();
    }

    // 前序遍历：根左右
    //
    public void preorderTraversal(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " "); // 先处理根节点
            preorderTraversal(root.left);     // 递归遍历左子树
            preorderTraversal(root.right);    // 递归遍历右子树
        }
    }

    // 中序遍历：左根右
    public void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);      // 递归遍历左子树
            System.out.print(root.val + " "); // 处理根节点
            inorderTraversal(root.right);     // 递归遍历右子树
        }
    }

    // 后序遍历：左右根
    public void postorderTraversal(TreeNode root) {
        if (root != null) {
            postorderTraversal(root.left);    // 递归遍历左子树
            postorderTraversal(root.right);   // 递归遍历右子树
            System.out.print(root.val + " "); // 处理根节点
        }
    }
}

